#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked

class Solution
{
public:
    int trap(vector<int> &height)
    {
        stack<int> monotonicStack;
        int ans = 0;
        for (int i = 0; i < height.size(); i++)
        {
            while (!monotonicStack.empty() && height[monotonicStack.top()] <= height[i]){
                int mid = monotonicStack.top();
                monotonicStack.pop();
                if(monotonicStack.empty()){
                    break;
                }
                int boundedHeight = min(height[monotonicStack.top()], height[i]) - height[mid];
                ans += boundedHeight * (i - monotonicStack.top() - 1);
            }
            monotonicStack.push(i);
        }
        return ans;
    }
};

int main()
{
    return 0;
}